//
// Created by Administrator on 2021/4/10.
//

/*
给定一棵二叉树，你需要计算它的直径长度。一棵二叉树的直径长度是任意两个结点路径长度中的最大值。这条路径可能穿过也可能不穿过根结点。


示例 :
给定二叉树

1
/ \
        2   3
/ \
      4   5
返回3, 它的长度是路径 [4,2,1,3] 或者[5,2,1,3]。


注意：两结点之间的路径长度是以它们之间边的数目表示。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/diameter-of-binary-tree
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。*/
#include <iostream>

using namespace std;

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;

    explicit TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}

    TreeNode(int x, TreeNode *l, TreeNode *r) : val(x), left(l), right(r) {}
};

class Solution {
    int ans = 0;  // 记录左右路径之和的最大值
public:
    int diameterOfBinaryTree(TreeNode *root) {
        // 树的直径为左子树最大深度 + 右子树最大深度
        depth(root);
        return ans - 1;
    }

    int depth(TreeNode *root) {
        if (root == nullptr) return 0;
        int L = depth(root->left);
        int R = depth(root->right);
        ans = max(ans, L + R + 1);
        return max(L, R) + 1;
    }
};

int main() {
    auto t5 = TreeNode(5);
    auto t4 = TreeNode(4);
    auto t3 = TreeNode(3);
    auto t2 = TreeNode(2, &t4, &t5);
    auto t1 = TreeNode(2, &t2, &t3);
    Solution sol;
    cout << sol.diameterOfBinaryTree(&t1);
    return 0;
}